
/*
N 叉树的层序遍历
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        //创建队列 先进先出特性
        Queue<Node> queue = new ArrayDeque<>();
        //将root放进队列中
        queue.offer(root);
        while(!queue.isEmpty()) {
            //计算此时queue里面的大小
            int n = queue.size();
            //用于存储每层节点数量
            List<Integer> list = new ArrayList<>();
            while(n != 0) {
                Node cur = queue.poll();
                list.add(cur.val);
                //将结点的孩子带进队列中
                for(Node x :cur.children) {
                    queue.offer(x);
                }
                n--;
            }
            //添加结果
            ret.add(list);
        }
        return ret;
    }
}
二叉树的锯齿形层序遍历
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q =  new ArrayDeque<>();
        q.offer(root);
        int i = 1;
        while(!q.isEmpty()) {
            int n = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            while(n-- != 0) {
                TreeNode cur = q.poll();
                list.add(cur.val);
                if(cur.left != null) {
                    q.offer(cur.left);
                }
                if(cur.right != null) {
                    q.offer(cur.right);
                }
            }
            if(i++ % 2 == 0) Collections.reverse(list);
            ret.add(list);
        }
        return ret;
    }
}
在每个树行中找最大值
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int max = Integer.MIN_VALUE;
        while(!q.isEmpty()) {
            int n = q.size();
            while(n-- != 0) {
                TreeNode cur = q.poll();
                max = Math.max(max,cur.val);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            ret.add(max);
            max = Integer.MIN_VALUE;
        }
        return ret;
    }
}
二叉树最大宽度
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        //存储pair 第一个值为node ，第二个值为它的编号
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        //先加入第一个节点
        q.add(new Pair<TreeNode,Integer>(root,1));
        //记录最终结果
        int ret = 0;
        while(!q.isEmpty()) {
            //记录每层的最大宽度
            //第一个位置
           Pair<TreeNode,Integer> t1 = q.get(0);
           //最后一个位置
           Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
           //更新结果
           ret = Math.max(ret,t2.getValue() - t1.getValue()+1);
           //创建新的q 保证每次记录的都是一层结果
           List<Pair<TreeNode,Integer>> tmp =  new ArrayList<>();
           for(Pair<TreeNode,Integer> t : q) {
                TreeNode cur = t.getKey();
                if(cur.left != null) {
                    tmp.add(new Pair<TreeNode,Integer>(cur.left,t.getValue()*2));
                }
                if(cur.right != null) {
                    tmp.add(new Pair<TreeNode,Integer>(cur.right,t.getValue()*2 + 1));
                }
           }
           //更新结果 让q 等于自己的下一层
           q = tmp;

        }
        return ret;
    }
}
 */